package study.datastructure.queue.impl;

import study.datastructure.queue.Deque;

import java.util.Iterator;

/**
 * 基于链表的双端队列实现
 */
public class LinkedListDeque<E> implements Deque<E>,Iterable<E> {
    private Node<E> head; // 头节点
    private Node<E> tail; // 尾节点
    private int size; // 当前队列大小
    private final int capacity; // 队列容量（如果需要限制容量）

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            Node<E> p=head;
            @Override
            public boolean hasNext() {
                return p!=null;
            }

            @Override
            public E next() {
                E value = p.data;
                p=p.next;
                return value;
            }
        };
    }


    /**
     * 链表节点类
     */
    class Node<E> {
        E data; // 节点数据
        Node<E> prev; // 前驱节点
        Node<E> next; // 后继节点

        Node(E data) {
            this.data = data;
            this.prev = null;
            this.next = null;
        }
    }


    // 构造函数，初始化双端队列
    public LinkedListDeque(int capacity) {
        this.head = null;
        this.tail = null;
        this.size = 0;
        this.capacity = capacity; // 如果需要设置容量限制，可以将其设置为0表示无限容量
    }

    // 允许无限容量
    public LinkedListDeque() {
        this(0); // 默认无容量限制
    }

    @Override
    public boolean offerFirst(E e) {
        if (e == null) throw new IllegalArgumentException("Element cannot be null");
        if (isFull()) return false; // 检查是否已满

        Node<E> newNode = new Node<>(e);
        if (head == null) { // 空队列
            head = newNode;
            tail = newNode;
        } else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
        size++;
        return true;
    }

    @Override
    public boolean offerLast(E e) {
        if (e == null) throw new IllegalArgumentException("Element cannot be null");
        if (isFull()) return false; // 检查是否已满

        Node<E> newNode = new Node<>(e);
        if (tail == null) { // 空队列
            head = newNode;
            tail = newNode;
        } else {
            newNode.prev = tail;
            tail.next = newNode;
            tail = newNode;
        }
        size++;
        return true;
    }

    @Override
    public E pollFirst() {
        if (isEmpty()) return null; // 空队列，返回null
        E data = head.data;
        head = head.next;
        if (head != null) {
            head.prev = null;
        } else {
            tail = null; // 如果队列变空，更新尾节点
        }
        size--;
        return data;
    }

    @Override
    public E pollLast() {
        if (isEmpty()) return null; // 空队列，返回null
        E data = tail.data;
        tail = tail.prev;
        if (tail != null) {
            tail.next = null;
        } else {
            head = null; // 如果队列变空，更新头节点
        }
        size--;
        return data;
    }

    @Override
    public E peekFirst() {
        return (head != null) ? head.data : null; // 返回头元素
    }

    @Override
    public E peekLast() {
        return (tail != null) ? tail.data : null; // 返回尾元素
    }

    @Override
    public boolean isEmpty() {
        return size == 0; // 判断队列是否为空
    }

    @Override
    public boolean isFull() {
        return capacity > 0 && size >= capacity; // 判断队列是否已满
    }

    // 返回队列当前大小
    public int size() {
        return size;
    }
}
